1. Field of the Invention
This invention relates to the field of data compression. More particularly, this invention relates to the field of data compression of the type in which blocks of input data are compressed into blocks of compressed data.
2. Description of the Prior Art
In some known data compression systems a quantiser is used to selectively remove information from the data as part of the compression process. A higher degree of quantisation will produce a higher degree of compression. In general, it is not possible to determine in advance what degree of compression will be produced by a particular degree of quantisation, since different portions of the input data may vary in information content and suitability for compression.
In some systems this is not a problem. For example, in a data compression system proposed by the Joint Photographic Experts Group image data is compressed using a quantiser and entropy encoder to a degree that varies upon the particular image and parameters used. The compressed image data is intended for non-real time processing and display, and accordingly, variations in the degree of compression achieved do not cause particular problems.
In another known data compression system input data is compressed with a quantiser and entropy encoder to effect temporal compression for the purpose of serial transmission. A data buffer is used to provide some time averaging of the degree of compression achieved. Compressed data is both continuously added to and removed from the buffer. If the buffer becomes too empty, or too full, then the degree of quantisation applied by the quantiser is changed to change the average rate of data flow into the buffer.
In contrast to the above, the problem of variation in the degree of compression achieved is particularly serious when compressing input data into blocks of a predetermined maximum size. The predetermined maximum size of the blocks of compressed data may be the result of the need to store each block of compressed data in a solid state memory or on magnetic tracks of fixed maximum capacity or the need to use the block of compressed data in a real-time transmission system with fixed maximum times for the processing of each block of compressed data. In such situations there is no flexibility in the maximum size of blocks of compressed data that can be accommodated. If too much compressed data is produced to fit into the fixed size block then an overrun with a consequential uncontrolled loss of data will occur.
To guard against this, the system can be set to have a degree of quantisation sufficient to ensure that all but the most information dense and difficult blocks of input data will compress to within the fixed size blocks.
Whilst the above solution is safe, it has the disadvantage that for most blocks of input data too high a level of quantisation is applied and more information is lost from the block of input data than was in fact necessary to fit the compressed data into its fixed size.
It is a constant aim of data compression systems to provide the degree of compression necessary for a given use with as low a loss in information from the input signal as is possible.
In co-pending UK patent application GB 9119985.1, filed on 19 September 1991 by the present applicant, there are described various examples of a data compression apparatus for compressing blocks of input data into blocks of compressed data having a predetermined maximum size, which data compression apparatus comprise a quantiser for applying a dynamically variable degree of quantisation to the blocks of input data to control the size of the blocks of compressed data to be substantially equal to the predetermined maximum size.
Header information which indicates the degree of quantisation applied is included in the blocks of compressed data so that on subsequent decompression the correct degree of dequantisation can subsequently be applied to the blocks of compressed data.
The apparatus described in GB 9119985.1 recognises that the variation in the degree of compression achieved with blocks of input data in general undergoes relatively small changes between adjacent blocks. For example, if the blocks of input data are successive fields of a video picture, then the changes in the scene depicted by the video field, and the information content of the video field, are relatively slow. In many other applications there are also relatively slowly changing information contents between blocks. Observation of different data streams will frequently show long runs of data sharing either high or low information content, e.g. long runs of zeros or low values followed by bursts of values of high information content. The apparatus described in GB 9119985.1 exploits this property by the application of dynamic control to the degree of quantisation applied to the input data. Dynamic control of the degree of quantisation reduces the average amount of information lost from the input data due to compression whilst guarding against overruns in the sizes of the blocks of compressed data.
The relationship between the degree of quantisation and the degree of compression is not a simple one and varies significantly on a number of factors including the information content of the block of input data being compressed. Various ways of achieving dynamic control of the degree of quantisation are described in GB 9119985.1.
In one approach an inter-block quantisation controller (i.e. a block quantisation controller which controls compression between blocks) uses a compression bit counter for storing a count of bits within blocks of compressed data. This is used to determine at the end of the compression of a block of input data what degree of quantisation the quantiser should apply to the next block of input data to control the size of the next block of compressed data to be substantially equal to the predetermined maximum size. The interblock quantisation controller determines a difference between the count of bits stored by the compressed bit counter and the predetermined maximum size and uses this difference to reference a memory storing data mapping differences to corresponding changes in degree of quantisation for reducing each difference value to substantially zero.
An alternative approach for dealing with this relationship is one in which the inter-block quantisation controller uses the count of bits stored by a compressed bit counter and a value indicating the current degree of quantisation to reference from a memory one of a plurality of sets of data which map degree of quantisation against degree of compression, and reads from the set of data what degree of quantisation the quantiser should apply to the block of input data to control the size of the block of compressed data to be substantially equal to said predetermined maximum size.
GB 9119985.1 explains that the degree of quantisation determined by the inter-block quantisation controller can be simply fed back to the quantiser for application to a subsequent block of input data. Other examples are also described where, for situations where a more exact inter-block control is required and in which time delay is not a critical problem, the inter-block quantisation controller also includes a test quantiser for applying a test degree of quantisation to each block of input data. The compressed bit counter is arranged to measure the degree of compression achieved with the test degree of quantisation. A delay circuit is provided For delaying arrival of said block of input data at the quantiser until the degree of quantisation determined by the inter-block quantisation controller is available for application by the quantiser to that block of input data.
GB 9119985.1 also describes another example in which the risk of overrun occurring can be further reduced by providing a desired occupancy indicator indicating the number of bits quantised in each block of input data and an intra-block quantisation controller (i.e. a quantisation controller fop dynamically varying the degree of quantisation within a block) which is responsive to the desired occupancy indicator. A compressed bit counter is used to determine what degree of quantisation the quantiser should apply to subsequent bits within the block of input data to control the size of the blocks of compressed data to be substantially equal to the predetermined maximum size. The quantiser applies said degree of quantisation determined by the intra-block quantisation controller to the subsequent bits within the block of input data.
The intra-block quantisation can be used in conjunction with inter-block quantisation. GB 9119985.1 describes an example where an accumulator stores a value indicative of the average degree of quantisation applied to a current block of input data, and a latch for reading the accumulator at the end of compression of each block of input data and serving as source of a base degree of quantisation to be applied to a subsequent block of input data.
The dynamic intra-block control described in co-pending application GB 9119985.1 works well in most situations. However, a problem has been identified where the block of data to be compressed has a degree of detail over the block which is not homogeneous. Consider, for example, the situation where the block of data to be compressed represents an image with relatively less image detail in the upper half (e.g. the sky) and relatively more detail in the lower half (e.g. the foreground). In such a situation, it has been found that the inter-block quantisation controller tends to apply a higher level of quantisation in the upper half of an image than is desirable and a lower level of quantisation in the lower part of the image than is desirable with the result that detail is lost in the lower part of the image.